//
// Created by weslywang on 2020/6/27.
//
#include "../common/common.h"

bool isDebug = true;

bool isPalindrome(string str) {
    if (str.size() < 1) {
        return false;
    }
    for (int i = 0, k = str.size() - 1; i < k; i++, k--) {
        if (str[i] != str[k]) {
            return false;
        }
    }
    return true;
}

bool dfs(vector<vector<int> > &list, int preLen, int pos, int &result, unordered_set<string> &blockList) {
    bool isFind = false;
    for (int i = list.size() - 1; i >= pos + 1; i--) {
        string str = to_string(pos) + "_" + to_string(i);
        if (list[pos][i] == 1) {
            bool aaa = preLen + 1 < result;
            if (i == list.size() - 1) {
                isFind = true;
                if (preLen + 1 < result) {
                    result = preLen + 1;
                }
            } else if (preLen + 1 < result) {
                preLen++;
                isFind = dfs(list, preLen, i, result, blockList);
                preLen--;
            }
//            if (!isFind && aaa) {
////                blockList.insert(str);
//                if (isDebug) {
////                    cout << "插入黑名单: " << str << endl;
//                }
//            }
        }

    }
    return isFind;
}

// 超时！！
int minCut(string s) {
    int numRows = s.length();
    vector<vector<int>> store(numRows, vector<int>(numRows));
    for (int i = 0; i < numRows; i++) {
        for (int k = i; k < numRows; k++) {
            string str = s.substr(i, k - i + 1);
            if (isPalindrome(str)) {
                store[i][k] = 1;
                if (isDebug) {
                    cout << "[" << i << "," << k << "] " << str << " true" << endl;
                }
            } else {
                store[i][k] = 0;
                if (isDebug) {
                    cout << "[" << i << "," << k << "] " << str << " false" << endl;
                }
            }
        }
    }

    if (isDebug) {
        cout << "开始" << endl;
    }
    unordered_set<string> blockList;
//    dfs(store, 0, 0, result, blockList);

    if (isDebug) {
        Common common;
        common.printVector(store);
    }
    vector<int> ans(s.size());
    for (int i = 0; i < s.size(); i++) {
        ans[i] = i;
        for (int k = 0; k <= i; k++) {
            if (s[i] == s[k] && (i - k < 2 || ((k + 1 <= i - 1) && store[k + 1][i - 1]))) {
                ans[i] = k == 0 ? 0 : min(ans[i], ans[k - 1] + 1);
            }
        }
    }
//    cout << "*结果 " << ans[s.size() - 1] << endl;
    return ans[s.size() - 1];
}

int minCut2(string s) {
    if (s.empty()) return 0;
    int n = s.size();
    vector<vector<bool>> p(n, vector<bool>(n));
    vector<int> dp(n);
    for (int i = 0; i < n; ++i) {
        dp[i] = i;
        for (int j = 0; j <= i; ++j) {
            if (s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])) {
                p[j][i] = true;
                dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
            }
        }
    }
    return dp[n - 1];
}

int main() {
    struct timeval start;
    struct timeval end;
    unsigned long timer;
    Common common;
    int a[] = {1, 2, 3, 4, 5};

//    cout << isPalindrome("ababababababababababababcbabababababababababababa") << endl;
    vector<string> inputList = common.loadStringData2();
    for (int i = 0; i < inputList.size(); i++) {
        cout << "原始长度：" << inputList[i].size() << endl;
        gettimeofday(&start, NULL);
//        int re = minCut(inputList[i]);
//        cout << "结果：" << re << endl;
        int re2 = minCut2(inputList[i]);
        cout << "结果：" << re2 << endl;
        gettimeofday(&end, NULL);
        timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
        cout << timer / 1000 << "毫秒" << endl;
        cout << "**************" << endl;
    }
    return 0;
}